package com.levi.recursion;

/**
 * @author shentong
 * @date 2021/8/29 21:46
 * @Description 递归实现迷宫
 * **递归三要素，
 * 1寻找递归子问题，这个时候【千万不要陷入细节思考】，默认递归函数已经帮你解决下面的问题了
 * 2寻找递归变化量，一般是没有思路的时候，就要加参数
 * 3 递归终止条件 防止爆栈**
 *
 * 1.先把地图做出来，一个二维数组，把墙建好
 */
public class Migong {
    public static void main(String[] args) {
        int[][] map = new int[8][7]; //8行7列
        //规定 1为墙，
        //先把第一行和第8行的元素全部设置为1,行不变，列移动
        for (int i = 0; i < map[0].length; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //先把第一列和第7列的元素全部设置为1 ，列不变，行移动
        for (int i = 0; i < map.length; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        //打印出迷宫
        System.out.println("建好墙之后的地图:------------");
        for (int[] ints : map) {
            for (int anInt : ints) {
                System.out.print(anInt+" ");
            }
            System.out.println();
        }
        System.out.println("小球走过的迷宫地图是:------------");
        findWay(map, 1, 1);
        for (int[] ints : map) {
            for (int anInt : ints) {
                System.out.print(anInt+" ");
            }
            System.out.println();
        }
    }

    /**
     *
     * @param map   地图
     * @param i    小球的初始横坐标  表示从map[i][j]做个坐标开始
     * @param j    小球得初始纵坐标
     * @return     是否找到了终点
     * 约定:
     * 1.map[6][5]为小球的终点，小球走到了这个坐标，则表示找到了终点，则返回true
     * 2.  0表示没有走过， 1表示墙，不能走，2表示可以走，3表示试过但是没有走通
     * 3.确定走迷宫的策略:下->右->上->左,如果该点走不通，再回溯
     */
    public static boolean findWay(int[][] map, int i, int j) {
        //如果找到了终点就退出
        if (map[6][5] == 2) {
            return true;
        }else{
            //如果没有找到终点就继续找
            if (map[i][j] == 0) {
                //先把该点设为2，假定该点可以走通
                map[i][j] = 2;
                //再尝试继续找，按照这个顺序【下->右->上->左】
                if (findWay(map, i + 1, j)) {//往下走
                    return true;
                } else if (findWay(map, i, j+1)) {//往右走
                    return true;
                }else if (findWay(map, i-1, j)) {//往上走
                    return true;
                }else if (findWay(map, i, j-1)) {//往左走
                    return true;
                }else {
                    //如果都走不通，是一条死路，就设置为3
                    map[i][j] = 3;
                    return false;
                }
            } else return false;
        }
    }
}
